package E_2024;

import java.util.Arrays;

/*
    书籍的长、宽都是整数对应 (l,w)。如果书A的长宽度都比B长宽大时，
    则允许将B排列放在A上面。现在有一组规格的书籍，书籍叠放时要求书籍不能做旋转，
    请计算最多能有多少个规格书籍能叠放在一起。
输入
    [[20,16],[15,11],[10,10],[9,10]]
输出
    3
    解释：前三本可叠放在一起。
 */
public class E_200_26 {
    public static void main(String[] args) {
        System.out.println(ans(new int[][]{{20,16},{10,10},{15,11},{9,10}}));
        System.out.println(ans(new int[][]{{20,16},{20,15},{19,16},{19,15},{9,10}}));
        System.out.println(ans(new int[][]{{20,20},{19,21},{18,20},{15,15}}));
    }
    public static int ans(int[][] arr){
        Arrays.sort(arr,(a,b)->{
            if (a[0] == b[0]) return a[1] - b[1];
            return a[0] - b[0];
//            return b[0]-a[0];
        });
        int[] dp = new int[arr.length+1];
        dp[1] = 1;
        for (int i = 1; i < arr.length; i++) {
            int[] temp = arr[i];
            for (int j = i; j >= 0; j--) {
                int[] x = arr[j];
                if (temp[1] > x[1] && temp[0] > x[0]){
                    dp[i+1] = Math.max(dp[i+1], dp[i - j] + 1);
                }
            }
        }
        return dp[arr.length];
    }
    public static int ans1(int[][] arr){
        Arrays.sort(arr,(a,b)->{
            if (a[0] == b[0]) return a[1] - b[1];
            return a[0] - b[0];
//            return b[0]-a[0];
        });
        for (int[] ints : arr) {
            System.out.println(Arrays.toString(ints));;
        }
        int ans = 1;
        int[] x = arr[0];
        for (int i = 1; i < arr.length; i++) {
            int[] temp = arr[i];
            if (temp[0] < x[0] && temp[1] < x[1]){
                ans++;
                x = temp;
            }
        }
        return ans;
    }
}
